# 方法1
# class Solution(object):
#     def sumSubarrayMins(self, arr):
#         base = 10 ** 9 + 7
#         n = len(arr)
#         pre = [-1] * n
#         ne = [-1] * n
#         st = []
#         for i in range(n):
#             while st and arr[st[-1]] >= arr[i]:
#                 st.pop()
#             if st:
#                 pre[i] = st[-1]
#             else:
#                 pre[i] = -1
#             st.append(i)
#         st = []
#         for i in range(n - 1, -1, -1):
#             while st and arr[st[-1]] > arr[i]:
#                 st.pop()
#             if st:
#                 ne[i] = st[-1]
#             else:
#                 ne[i] = n
#             st.append(i)
#         t = 0
#         for i in range(n):
#             t = (t + arr[i] * (ne[i] - i) * (i - pre[i])) % base
#         return t

# 方法2
class Solution(object):
    def sumSubarrayMins(self, arr):
        mod = 10 ** 9 + 7
        ans = 0
        dot = 0
        st = []
        n = len(arr)
        for i in range(n):
            count = 1
            while st and st[-1][0] >= arr[i]:
                count += st[-1][1]
                dot -= st[-1][1] * st[-1][0]
                st.pop()
            st.append([arr[i], count])
            dot += arr[i] * count
            ans = (ans + dot) % mod
        return ans
        

data = Solution()
arr = [3, 1, 2, 4]
print(data.sumSubarrayMins(arr))
